package 搜索算法.深度优先搜索;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 1. 问题描述
 *      n块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。
 *      如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。
 *      给你一个长度为 n 的数组 stones ，其中 stones[i] = [xi, yi] 表示第 i 块石头的位置，返回 可以移除的石子 的最大数量。
 *
 * 2. 算法分析
 *      DFS实现(深度优先搜索，当然可以非递归实现，但是我们可以利用底层的方法栈来实现递归，无需手动使用栈来模拟，代码简洁)
 *      我们将二维平面上的坐标看成点，将问题转化为图来实现
 *      如果两个坐标的行坐标或者列坐标相同，我们将这两个点之间看做是有边的，其他的则视为无边的
 *      问题之一：我们如何存放这个图?采用什么数据结构呢?
 *          1. 采用二维数组
 *          2. 采用list容器来存放
 *
 *      分析dfs过程：
 *          我们的目的是求出图中的所有连通分量的数量，从图中一个点开始，如果存在一个点和当前点有边，则下一次搜索从与当前点
 *          相连的点(注意这个点之前没有被访问)开始进行下一次的dfs过程，如果没有边与之相连，则当前节点可以看成是一个孤立点
 *
 *          每次dfs都会找到以当前没有被访问的节点的为起始点的连通分量，所以每调用一次dfs都会找到一个连通分量
 *
 *      最终的结果 = 所有的石头的数量 - 图中的所有连通分量的数量
 *
 *      分析方法dfs的参数：
 *          1. 访问数组(因为需要知道访问状态)
 *          2. 当前起始节点索引
 *          3. 图中点与点之间的边的信息
 *
 *
 *      时间复杂度和空间复杂度分析：
 *          对于空间复杂度我们额外使用了 n^2 的数组来存放边的信息，还有一个n的访问数组
 *          所以空间复杂度为O(n^2)
 *
 *          对于时间复杂度，
 *              1. 初始化边数组 O(n^2)
 *              2. dfs递归过程
 *                  由于采用的是二维数组来存放图，而每一个点至多被访问一次，所以点的访问为O(n^2)
 *
 *
 *     下面我们采用list容器来存放图的边的信息
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 移除最多的同行或者同列的石头 {

    /*采用二维数组存放图*/
    /**
     * 采用二维数组存放的图的信息
     * @param stones
     * @return
     */
    public int removeStones1(int[][] stones) {
        int stoneCounts = stones.length; // 石头的数量，从0开始编号
        int[][] edges = new int[stoneCounts][stoneCounts]; // 存放边的二维数组
        // 初始化边矩阵
        for (int i = 0; i < stoneCounts; i++) {
            for (int j = 0; j < stoneCounts; j++) {
                if ((stones[i][0] == stones[j][0]) || (stones[i][1] == stones[j][1])) {
                    edges[i][j] = 1;
                    edges[j][i] = 1;
                }
            }
        }
        // dfs过程
        boolean[] visited = new boolean[stoneCounts]; // 访问数组
        int connectionCounts = 0; // 记录连通分量的数量
        for (int i = 0; i < stoneCounts; i++) {
            if (visited[i] == false) { // 如果当前点没有被访问
                connectionCounts++;
                dfs1(edges,visited,i);
            }
        }
        return stoneCounts - connectionCounts;
    }

    /**
     * 深度优先遍历  采用二维数组实现的图的存储
     * @param edges：边信息
     * @param visited：访问状态数组
     * @param curVertex：当前点
     */
    public void dfs1(int[][] edges,boolean[] visited,int curVertex) {
        visited[curVertex] = true; // 修改当前点的访问状态
        for (int i = 0; i < edges.length; i++) {
            if (visited[i] == false && edges[i][curVertex] == 1) {
                dfs1(edges,visited,i);
            }
        }
    }



    /*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
    /*采用list容器来存放图*/

    /**
     * 如果采用list来存放边的信息 List<List<Integer>> 第i个list容器存放与第i个点相连的所有点，这些点通过list来存放
     * 类似于邻接表的方式存放，节省内存，并且效率上要快于使用二维数组的方式
     * @param stones
     * @return
     */
    public int removeStones2(int[][] stones) {
        int stoneCounts = stones.length;
        List<List<Integer>> edges = new ArrayList<>();
        // 初始化边信息
        for (int i = 0; i < stoneCounts; i++) {
            List<Integer> temp = new ArrayList<>();
            edges.add(temp);
            for (int j = 0; j < stoneCounts; j++) {
                if ((stones[i][0] == stones[j][0]) || (stones[i][1] == stones[j][1])) {
                    edges.get(i).add(j);
                }
            }
        }

        // dfs
        int connectionCounts = 0;
        boolean[] visited = new boolean[stoneCounts];
        for (int i = 0; i < stoneCounts; i++) {
            if (visited[i] == false) {
                connectionCounts++;
                dfs2(i,edges,visited);
            }
        }
        return stoneCounts - connectionCounts;
    }

    public void dfs2(int x,List<List<Integer>> edges,boolean[] visited) {
        visited[x] = true;
        for(int y : edges.get(x)) { // 从当前点x的边查询不需要扫描所有点
            if(visited[y] == false) {
                dfs2(y,edges,visited);
            }
        }
    }


    /*+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
    /*非递归实现*/
    public int removeStones3(int[][] stones) {
        int stoneCounts = stones.length;
        List<List<Integer>> edges = new ArrayList<>();
        // 初始化边信息
        for (int i = 0; i < stoneCounts; i++) {
            List<Integer> temp = new ArrayList<>();
            edges.add(temp);
            for (int j = 0; j < stoneCounts; j++) {
                if ((stones[i][0] == stones[j][0]) || (stones[i][1] == stones[j][1])) {
                    edges.get(i).add(j);
                }
            }
        }
        // 采用栈模拟
        Stack<Integer> stack = new Stack<>();
        int connectionCounts = 0;
        boolean[] visited = new boolean[stoneCounts];
        for(int x = 0; x < stoneCounts; x++) {
            if(visited[x] == false) {
                stack.add(x);
                visited[x] = true;
                while(!stack.isEmpty()) {
                    int cur = stack.pop();
                    for(int y : edges.get(cur)) {
                        if(visited[y] == false) {
                            stack.add(y);
                            visited[y] = true;
                        }
                    }
                }
                connectionCounts++;
            }
        }
        return stoneCounts - connectionCounts;
    }
}
